Section: New Results

Finding long and multiple repeats with edit distance

We developed an algorithm, FilmRed , for detecting long similar fragments occurring at least twice in a set of biological sequences (a conference paper [25] has already appeared, a journal version is in preparation). The problem becomes computationally challenging when a non negligible number of insertions, deletions and substitutions are allowed. The algorithm is exact and manages instances whose size and combination of parameters cannot be handled by other currently existing method. This is achieved by using a filter as a preprocessing step, and then the information that this filter has gathered in the following inference phase. FilmRed can deal with very long repeats (up to a few thousands) occurring possibly several times, with a difference rate (substitutions and indels) of 10% or more. This work was done in collaboration with N. Pisanti and P. Peterlongo. The software will be made available in a near future.